
#include "bisearch.h"
#include <fstream>
#include <chrono>
#include <limits>

bTrans::bTrans(std::string filename) {
    std::ifstream infile(filename);
    int u, v;
    std::string help;
    time_t t, w = 1;
    std::set<std::tuple<int, time_t, inout>> check;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            m++;
            edges[m] = tEdge(m, std::make_tuple(u, t, OUT), std::make_tuple(v, t + w, IN), w);
            out[{u, t, OUT}].insert(m);
            in[{v, t + w, IN}].insert(m);
            outtimes[u].insert(t);
            intimes[v].insert(t + w);
        }
    }
    for (auto& [k, v]: intimes) {
        for (auto it = v.begin(); it != v.end(); it++) {
            if (next(it) != v.end()) {
                m++;
                edges[m] = tEdge(m, std::make_tuple(k, *it, IN), std::make_tuple(k, *next(it), OUT), 0);
                out[{k, *it, IN}].insert(m);
                in[{k, *next(it), IN}].insert(m);
            }
        }
        for (auto it = v.rbegin(); it != v.rend(); it++) {
            auto it2 = outtimes[k].lower_bound(*it);
            if (it2 == outtimes[k].end())   continue;
            if (check.contains({k, *it2, OUT})) continue;
            m++;
            edges[m] = tEdge(m, std::make_tuple(k, *it, IN), std::make_tuple(k, *it2, OUT), 0);
            out[{k, *it, IN}].insert(m);
            in[{k, *it2, OUT}].insert(m);
            check.insert({k, *it, OUT});
        }
    }
    for (auto& [k, v]: outtimes) {
        for (auto it = v.begin(); it != v.end(); it++) {
            if (next(it) != v.end()) {
                m++;
                edges[m] = tEdge(m, std::make_tuple(k, *it, OUT), std::make_tuple(k, *next(it), OUT), 0);
                out[{k, *it, OUT}].insert(m);
                in[{k, *next(it), OUT}].insert(m);
            }
        }
    }
}

void bTrans::search1(int source, int target, time_t start, time_t end) {
    dis1.clear();
    f.clear();
    std::vector<int> hello;
    for (auto time: outtimes[source]) {
        if (time >= start && time <= end) {
            m++;
            tEdge temp_edge = {m, {source, start, SUPER}, {source, time, OUT}, 0};
            edges[m] = temp_edge;
            out[{source, start, SUPER}].insert(m);
            in[{source, time, OUT}].insert(m);
            hello.push_back(m);
        }
    }
    pq1.emplace(0, start, SUPER, source);
    while (!pq1.empty()) {
        auto [d, t, inout, u] = pq1.top();
        pq1.pop();
        if (dis1.contains({u, t, inout})) continue;
        dis1[{u, t, inout}] = d;
        if (!f.contains(u)) f[u] = d;
        if (u == target) break;
        for (auto neid: out[{u, t, inout}]) {
            auto& nedge = edges[neid];
            auto [nv, nvt, nvout] = nedge.v;
            if (dis1.contains({nv, nvt, nvout}))    continue;
            if (nvt >= start && nvt <= end) {
                pq1.emplace(d + nedge.w, nvt, nvout, nv);
            }
        }
    }
    for (auto eid: hello) {
        out[edges[eid].u].erase(eid);
        in[edges[eid].v].erase(eid);
        edges.erase(eid);
    }
    out.erase({source, start, SUPER});
}

void bTrans::search2(int source, time_t start, time_t end) {
    dis1.clear();
    f.clear();
    std::vector<int> hello;
    for (auto time: intimes[source]) {
        if (time >= start && time <= end) {
            m++;
            tEdge temp_edge = {m, {source, time, IN}, {source, end, SUPER}, 0};
            edges[m] = temp_edge;
            out[{source, time, IN}].insert(m);
            in[{source, end, SUPER}].insert(m);
            hello.push_back(m);
        }
    }
    pq1.emplace(0, end, SUPER, source);
    while (!pq1.empty()) {
        auto [d, t, inout, u] = pq1.top();
        pq1.pop();
        if (dis1.contains({u, t, inout})) continue;
        dis1[{u, t, inout}] = d;
        if (!f.contains(u)) f[u] = d;
        for (auto neid: in[{u, t, inout}]) {
            auto& nedge = edges[neid];
            auto [nu, nut, nuout] = nedge.u;
            if (dis1.contains({nu, nut, nuout}))    continue;
            if (nut >= start && nut <= end) {
                pq1.emplace(d + nedge.w, nut, nuout, nu);
            }
        }
    }
    for (auto eid: hello) {
        out[edges[eid].u].erase(eid);
        in[edges[eid].v].erase(eid);
        edges.erase(eid);
    }
    in.erase({source, end, SUPER});
}

int bTrans::bisearch(int source, int target, time_t start, time_t end) {
    dis1.clear();
    dis2.clear();
    f.clear();
    std::vector<int> hello;
    for (auto time: outtimes[source]) {
        if (time >= start && time <= end) {
            m++;
            tEdge temp_edge = {m, {source, start, SUPER}, {source, time, OUT}, 0};
            edges[m] = temp_edge;
            out[{source, start, SUPER}].insert(m);
            in[{source, time, OUT}].insert(m);
            hello.push_back(m);
        }
    }
    for (auto time: intimes[target]) {
        if (time >= start && time <= end) {
            m++;
            tEdge temp_edge = {m, {target, time, IN}, {target, end, SUPER}, 0};
            edges[m] = temp_edge;
            out[{target, time, IN}].insert(m);
            in[{target, end, SUPER}].insert(m);
            hello.push_back(m);
        }
    }
    int ans = -1;
    pq1.emplace(0, start, SUPER, source);
    pq2.emplace(0, end, SUPER, target);
    while (!pq1.empty() && !pq2.empty()) {
        {
            int a = std::get<0>(pq1.top());
            int b = std::get<0>(pq2.top());
            if (ans != -1 && ans <= a + b) {
//                std::cout << "free!" << std::endl;
                break;
            }
        }
        {
            auto [d, t, io, u] = pq1.top();
            pq1.pop();
            if (!dis1.contains({u, t, io})) {
                dis1[{u, t, io}] = d;
                if (u == target)    return d;
                for (auto neid: out[{u, t, io}]) {
                    auto& nedge = edges[neid];
                    auto [nv, nvt, nvout] = nedge.v;
                    if (dis1.contains({nv, nvt, nvout}))    continue;
                    if (nvt >= start && nvt <= end) {
                        pq1.emplace(d + nedge.w, nvt, nvout, nv);
                    }
                    if (dis2.contains({nv, nvt, nvout})) {
                        if (ans == -1 || ans > d + nedge.w + dis2[{nv, nvt, nvout}]) {
                            ans = d + nedge.w + dis2[{nv, nvt, nvout}];
                        }
                    }
                }
            }
        }
        {
            auto [d, t, io, u] = pq2.top();
            pq2.pop();
            if (!dis2.contains({u, t, io})) {
                dis2[{u, t, io}] = d;
                if (u == source)    return d;
                for (auto neid: in[{u, t, io}]) {
                    auto& nedge = edges[neid];
                    auto [nu, nut, nuout] = nedge.u;
                    if (dis2.contains({nu, nut, nuout}))    continue;
                    if(nut >= start && nut <= end) {
                        pq2.emplace(d + nedge.w, nut, nuout, nu);
                    }
                    if (dis1.contains({nu, nut, nuout})) {
                        if (ans == -1 || ans > d + nedge.w + dis1[{nu, nut, nuout}]) {
                            ans = d + nedge.w + dis1[{nu, nut, nuout}];
                        }
                    }
                }
            }
        }
    }
    for (auto eid: hello) {
        out[edges[eid].u].erase(eid);
        in[edges[eid].v].erase(eid);
        edges.erase(eid);
    }
    out.erase({source, start, SUPER});
    in.erase({target, end, SUPER});
    return ans;
}


bDij::bDij(std::string filename) {
    std::ifstream infile(filename);
    int u, v;
    std::string help;
    time_t t, w = 1;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            m++;
            edges[m] = {m, u, v, t, w};
            out[u].emplace(m, u, v, t, w);
            in[v].emplace(m, u, v, t, w);
        }
    }
}

void bDij::search1(int source, int target, time_t start, time_t end) {
    dis1.clear();
    f.clear();
    pq1.emplace(0, start, source);
    while (!pq1.empty()) {
        auto [d, t, u] = pq1.top();
        pq1.pop();
        if (dis1.contains(u)) {
            if (!dis1[u].empty()) {
                auto [ft, fd] = *dis1[u].begin();
                if (ft <= t)    continue;
            }
        }
        dis1[u].insert(dis1[u].begin(), std::make_pair(t, d));
        if (!f.contains(u)) f[u] = d;
        if (u == target) return;
        if (!out.contains(u))   continue;
        Edge faker = {0, 0, 0, t, 0};
        for (auto it = out[u].lower_bound(faker); it != out[u].end(); it++) {
            auto& [neid, nu, nv, nt, nw] = *it;
            if (nt > end)   break;
            if (nt + nw > end)  continue;
            if (dis1.contains(nv)) {
                if (!dis1[u].empty()) {
                    auto [ft, fd] = *dis1[nv].begin();
                    if (ft <= nt + nw)    continue;
                }
            }
            pq1.emplace(d + nw, nt + nw, nv);
        }
    }
    return;
}

void bDij::search2(int source, time_t start, time_t end) {
    dis1.clear();
    f.clear();
    pq2.emplace(0, end, source);
    while (!pq2.empty()) {
        auto [d, t, u] = pq2.top();
        pq2.pop();
        if (dis1.contains(u)) {
            if (!dis1[u].empty()) {
                auto [ft, fd] = *dis1[u].rbegin();
                if (ft >= t)    continue;
            }
        }
        dis1[u].insert(dis1[u].end(), std::make_pair(t, d));
        if (!f.contains(u)) f[u] = d;
        if (!in.contains(u))   continue;
        for (auto it = in[u].lower_bound({0, 0, 0, start, 0}); it != in[u].upper_bound({0, 0, 0, t, 0}); it++) {
            auto& [neid, nu, nv, nt, nw] = *it;
            if (nt < start) continue;
            if (dis1.contains(nu)) {
                if (!dis1[u].empty()) {
                    auto [ft, fd] = *dis1[nu].rbegin();
                    if (ft <= nt)   continue;
                }
            }
            pq2.emplace(d + nw, nt, nu);
        }
    }
    return;
}

int bDij::bisearch(int source, int target, time_t start, time_t end) {
    dis1.clear();
    dis2.clear();
    int ans = -1;
    pq1.emplace(0, start, source);
    pq2.emplace(0, end, target);
    while (!pq1.empty() && !pq2.empty()) {
        {
            int a = std::get<0>(pq1.top());
            int b = std::get<0>(pq2.top());
            if (ans != -1 && ans <= a + b)  break;
        }
        {
            auto [d, t, u] = pq1.top();
            pq1.pop();
            if (dis1.contains(u)) {
                if (!dis1[u].empty()) {
                    auto [ft, fd] = *dis1[u].begin();
                    if (ft <= t)    continue;
                }
            }
            if (u == target)    return d;
            dis1[u].insert(dis1[u].begin(), std::make_pair(t, d));
            if (!out.contains(u))   continue;
            Edge faker = {0, 0, 0, t, 0};
            for (auto it = out[u].lower_bound(faker); it != out[u].end(); it++) {
                auto& [neid, nu, nv, nt, nw] = *it;
                if (nt > end)   break;
                if (nt + nw > end)  continue;
                if (dis1.contains(nv)) {
                    if (!dis1[nv].empty()) {
                        auto [ft, fd] = *dis1[nv].begin();
                        if (ft <= nt + nw)    continue;
                    }
                }
                pq1.emplace(d + nw, nt + nw, nv);
                if (dis2.contains(nv)) {
                    auto it2 = dis2[nv].lower_bound(nt + nw);
                    if (it2 != dis2[nv].end()) {
                        if (ans == -1 || ans > d + nw + it2->second) {
                            ans = d + nw + it2->second;
                        }
                    }
                }
            }
        }
        {
            auto [d, t, u] = pq2.top();
            pq2.pop();
            if (dis2.contains(u)) {
                if (!dis2[u].empty()) {
                    auto [ft, fd] = *dis2[u].rbegin();
                    if (ft >= t)    continue;
                }
            }
            dis2[u].insert(dis2[u].end(), std::make_pair(t, d));
            if (u == source)    return d;
            if (!in.contains(u))   continue;
            auto bound = in[u].upper_bound({0, 0, 0, t, 0});
            for (auto it = in[u].upper_bound({0, 0, 0, start, 0}); it != bound; it++) {
                auto& [neid, nu, nv, nt, nw] = *it;
                if (nt < start) continue;
                if (dis2.contains(nu)) {
                    if (!dis2[nu].empty()) {
                        auto [ft, fd] = *dis2[nu].rbegin();
                        if (ft >= nt)   continue;
                    }
                }
                pq2.emplace(d + nw, nt, nu);
                if (dis1.contains(nu)) {
                    auto it2 = dis1[nu].upper_bound(nt);
                    if (it2 != dis1[nu].begin()) {
                        if (ans == -1 || ans > d + nw + prev(it2)->second) {
                            ans = d + nw + prev(it2)->second;
                        }
                    }
                }
            }
        }
    }
    return ans;
}

void help1(std::string filename) {
    std::srand(unsigned(std::time(0)));
    ADJ adj(filename);
    std::vector<int> sf(adj.vertices.begin(), adj.vertices.end());
    std::random_shuffle(sf.begin(), sf.end());
    bTrans test(filename);
    sf[0] = 1401;
    sf[1] = 5739;
    int cnt1 = 0;
    int cnt2 = 0;
    for (int i = 0; i < 2000; i += 2) {
        while(!test.pq1.empty()) test.pq1.pop();
        while(!test.pq2.empty()) test.pq2.pop();
//        test = bTrans(filename);
        auto start1 = std::chrono::system_clock::now();
        test.search1(sf[i], sf[i + 1], 0, std::numeric_limits<time_t>::max());
        auto end1 = std::chrono::system_clock::now();
        auto duration1 = duration_cast<std::chrono::microseconds>(end1 - start1);
        auto hello1 = test.f[sf[i + 1]];

//        test = bTrans(filename);
//        auto start2 = std::chrono::system_clock::now();
//        test.search2(sf[i + 1], 0, std::numeric_limits<time_t>::max());
//        auto end2 = std::chrono::system_clock::now();
//        auto duration2 = duration_cast<std::chrono::microseconds>(end2 - start2);
//        auto hello2 = test.f[sf[i]];

//        test = bTrans(filename);
        auto start3 = std::chrono::system_clock::now();
        auto hello3 = test.bisearch(sf[i], sf[i + 1], 0, std::numeric_limits<time_t>::max());
        auto end3 = std::chrono::system_clock::now();
        auto duration3 = duration_cast<std::chrono::microseconds>(end3 - start3);
//        std::cout << sf[i] << " " << sf[i + 1] << std::endl;
//        std::cout << hello1 << " " << hello2 << " " << std::endl;
//        std::cout << hello1 << " " << hello2 << " " << hello3 << std::endl;
//        std::cout << sf[i] << " " << sf[i + 1] << " " << duration1.count() << " " << duration2.count() << " " << duration3.count() << std::endl;
        if (hello1 != 0 && duration3.count() < duration1.count()) {
            cnt1++;
        }
        if (hello1 != 0) {
            cnt2++;
        }
    }
    std::cout << cnt1 << " " << cnt2 << std::endl;
}

void help2(std::string filename) {
    std::srand(unsigned(std::time(0)));
    ADJ adj(filename);
    std::vector<int> sf(adj.vertices.begin(), adj.vertices.end());
    std::random_shuffle(sf.begin(), sf.end());
    bDij test(filename);
    int cnt1 = 0;
    int cnt2 = 0;
    int cnt3 = 0;
    for (int i = 0; i < 2000; i += 2) {
        while(!test.pq1.empty()) test.pq1.pop();
        while(!test.pq2.empty()) test.pq2.pop();
        auto start1 = std::chrono::system_clock::now();
        test.search1(sf[i], sf[i + 1], 0, std::numeric_limits<time_t>::max());
        auto end1 = std::chrono::system_clock::now();
        auto duration1 = duration_cast<std::chrono::microseconds>(end1 - start1);
        auto hello1 = test.f[sf[i + 1]];
//        std::cout << "done!";

//        test = bDij(filename);
//        auto start2 = std::chrono::system_clock::now();
//        test.search2(sf[i + 1], 0, std::numeric_limits<time_t>::max());
//        auto end2 = std::chrono::system_clock::now();
//        auto duration2 = duration_cast<std::chrono::microseconds>(end2 - start2);
//        auto hello2 = test.f[sf[i]];

        auto start3 = std::chrono::system_clock::now();
        auto hello3 = test.bisearch(sf[i], sf[i + 1], 0, std::numeric_limits<time_t>::max());
        auto end3 = std::chrono::system_clock::now();
        auto duration3 = duration_cast<std::chrono::microseconds>(end3 - start3);

        if (hello1 != hello3 && (hello1!=0 && hello3!=-1)) {
            std::cout << sf[i] << " " << sf[i + 1] << std::endl;
            std::cout << hello1 << " " << hello3 << std::endl;
            std::cout << "error!" << std::endl;
        }

//        std::cout << sf[i] << " " << sf[i + 1] << " " << duration1.count() << " " << duration3.count() << std::endl;
        if (hello1 != 0 && duration3.count() < duration1.count()) {
            cnt1++;
        }
        if (hello1 != 0) {
            cnt2++;
        }
        if (duration3.count() < duration1.count()) {
            cnt3++;
        }
    }
    std::cout << cnt1 << " " << cnt2 << " " << cnt3 << std::endl;
}

bfDij::bfDij(std::string filename) {
    std::ifstream infile(filename);
    int u, v;
    std::string help;
    time_t t, w = 1;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            m++;
            edges[m] = {m, u, v, t, w};
            out[u].emplace(m, u, v, t, w);
            in[v].emplace(m, u, v, t, w);
        }
    }
}

void bfDij::search1(int source, int target, time_t start, time_t end) {
    while(!pq1.empty()) pq1.pop();
    dis1.clear();
    f.clear();
    pq1.emplace(start, source);
    while (!pq1.empty()) {
        auto [t, u] = pq1.top();
        pq1.pop();
        if (dis1.contains(u))   continue;
        f[u] = t;
        if (u == target) break;
        if (!out.contains(u))   continue;
        for (auto it = out[u].lower_bound({0, 0, 0, t, 0}); it != out[u].end(); it++) {
            auto& edge = *it;
            if (edge.t > end)   break;
            if (edge.t + edge.w > end)  continue;
            if (f.contains(edge.v)) continue;
            pq1.emplace(edge.t + edge.w, edge.v);
        }
    }
}

int bfDij::bisearch(int source, int target, time_t start, time_t end) {
    dis1.clear();
    dis2.clear();
    pq1.emplace(start, source);
    pq2.emplace(end, target);
    while (!pq1.empty() && !pq2.empty()) {
        {
            auto [t1, u1] = pq1.top();
            auto [t2, u2] = pq2.top();
            if (t1 > t2)   break;
        }
        {
            auto [t, u] = pq1.top();
            pq1.pop();
            if (dis1.contains(u))   continue;
            if (u == target) return 1;
            if (!out.contains(u))   continue;
            for (auto it = out[u].lower_bound({0, 0, 0, t, 0}); it != out[u].end(); it++) {
                auto& edge = *it;
                if (edge.t > end)   break;
                if (edge.t + edge.w > end)  continue;
                if (dis2.contains(edge.v)) return 1;
                if (dis1.contains(edge.v)) continue;
                pq1.emplace(edge.t + edge.w, edge.v);
            }
        }
        {
            auto [t, u] = pq2.top();
            pq2.pop();
            if (dis2.contains(u))   continue;
            if (u == source) return 1;
            if (!in.contains(u))   continue;
            auto bound = in[u].upper_bound({0, 0, 0, t, 0});
            for (auto it = in[u].upper_bound({0, 0, 0, start, 0}); it != bound; it++) {
                auto& edge = *it;
                if (edge.t < start) continue;
                if (dis1.contains(edge.u)) return 1;
                if (dis2.contains(edge.u)) continue;
                pq2.emplace(edge.t, edge.u);
            }
        }
    }
    return -1;
}

bfTrans::bfTrans(std::string filename) {
    std::ifstream infile(filename);
    int u, v;
    std::string help;
    time_t t, w = 1;
    std::set<std::tuple<int, time_t, inout>> check;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            m++;
            edges[m] = tEdge(m, std::make_tuple(u, t, OUT), std::make_tuple(v, t + w, IN), w);
            out[{u, t, OUT}].insert(m);
            in[{v, t + w, IN}].insert(m);
            outtimes[u].insert(t);
            intimes[v].insert(t + w);
        }
    }
    for (auto& [k, v]: intimes) {
        for (auto it = v.begin(); it != v.end(); it++) {
            if (next(it) != v.end()) {
                m++;
                edges[m] = tEdge(m, std::make_tuple(k, *it, IN), std::make_tuple(k, *next(it), OUT), 0);
                out[{k, *it, IN}].insert(m);
                in[{k, *next(it), IN}].insert(m);
            }
        }
        for (auto it = v.rbegin(); it != v.rend(); it++) {
            auto it2 = outtimes[k].lower_bound(*it);
            if (it2 == outtimes[k].end())   continue;
            if (check.contains({k, *it2, OUT})) continue;
            m++;
            edges[m] = tEdge(m, std::make_tuple(k, *it, IN), std::make_tuple(k, *it2, OUT), 0);
            out[{k, *it, IN}].insert(m);
            in[{k, *it2, OUT}].insert(m);
            check.insert({k, *it, OUT});
        }
    }
    for (auto& [k, v]: outtimes) {
        for (auto it = v.begin(); it != v.end(); it++) {
            if (next(it) != v.end()) {
                m++;
                edges[m] = tEdge(m, std::make_tuple(k, *it, OUT), std::make_tuple(k, *next(it), OUT), 0);
                out[{k, *it, OUT}].insert(m);
                in[{k, *next(it), OUT}].insert(m);
            }
        }
    }
}

int bfTrans::search1(int source, int target, time_t start, time_t end) {
    dis1.clear();
    while(!q1.empty()) q1.pop();
    if (source == target) return 1;
    if (outtimes.contains(source)) {
        for (auto it = outtimes[source].lower_bound(start); it != outtimes[source].upper_bound(end); it++) {
            q1.emplace(source, *it, OUT);
            dis1.emplace(source, *it, OUT);
        }
    }
    while (!q1.empty()) {
        auto [u, t, d] = q1.front();
        for (auto eid: out[{u, t, d}]) {
            auto& edge = edges[eid];
            if (std::get<1>(edge.v) >= start && std::get<1>(edge.v) <= end) {
                if (dis1.contains(edge.v))  continue;
                if (std::get<0>(edge.v) == target) return 1;
                dis1.emplace(edge.v);
                q1.emplace(edge.v);
            }
        }
    }
    return -1;
}

int bfTrans::bisearch(int source, int target, time_t start, time_t end) {
    dis1.clear();
    dis2.clear();
    while(!q1.empty()) q1.pop();
    while(!q2.empty()) q2.pop();
    if (source == target) return 1;
    if (outtimes.contains(source)) {
        for (auto it = outtimes[source].lower_bound(start); it != outtimes[source].upper_bound(end); it++) {
            q1.emplace(source, *it, OUT);
            dis1.emplace(source, *it, OUT);
        }
    }
    if (intimes.contains(target)) {
        for (auto it = intimes[target].lower_bound(start); it != intimes[target].upper_bound(end); it++) {
            q2.emplace(target, *it, IN);
            dis2.emplace(target, *it, IN);
        }
    }
    while (!q1.empty() && !q2.empty()) {
        {
            auto [u, t, d] = q1.front();
            for (auto eid: out[{u, t, d}]) {
                auto& edge = edges[eid];
                if (std::get<1>(edge.v) >= start && std::get<1>(edge.v) <= end) {
                    if (dis1.contains(edge.v))  continue;
                    if (std::get<0>(edge.v) == target) return 1;
                    if (dis2.contains(edge.v)) return 1;
                    dis1.emplace(edge.v);
                    q1.emplace(edge.v);
                }
            }
        }
        {
            auto [u, t, d] = q2.front();
            for (auto eid: in[{u, t, d}]) {
                auto& edge = edges[eid];
                if (std::get<1>(edge.u) >= start && std::get<1>(edge.u) <= end) {
                    if (dis2.contains(edge.u))  continue;
                    if (std::get<0>(edge.u) == source) return 1;
                    if (dis1.contains(edge.u)) return 1s
                    dis2.emplace(edge.u);
                    q2.emplace(edge.u);
                }
            }
        }
    }
    return -1;
}


